# 动态规划 —> 求最值问题
# 明确状态、明确选择、明确dp数组/函数的意义、明确base case
# 通过dp函数求解：自顶而下
# 通过dp数组求解：自底而上
MAX_UINT = 65536

# 斐波那契数 0 1 1 2 3 5 8 13 21 ...
# 自顶向下的递归解法
# def fib(N):
#     # 备忘录
#     memo = [-1 for _ in range(N+1)]
#     def dp(n):
#         if n == 0 or n == 1: return n
#         if memo[n] != -1: return memo[n]
#         memo[n] = dp(n-1) + dp(n-2)
#         return memo[n]
#
#     return dp(N)

# 自底而上的迭代解法
def fib(N):
    if N == 0: return 0
    dp = [0 for _ in range(N+1)]
    dp[1] = 1

    for i in range(2, N+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[N]

N = 20
print("{}的斐波那契数为 {}".format(N, fib(N)))

# 凑零钱问题
# 自顶而下
# def coinChange(coins, amount):
#     # 备忘录 注意备忘录里存放的内容和dp数组完全一样的，只是将递归改成了for遍历
#     memo = [-666 for _ in range(amount+1)]
#
#     def dp(amount):  # 凑成当前amount至少需要多少硬币？
#         # base case
#         if amount == 0: return 0
#         if amount < 0: return -1
#
#         # check memo
#         if memo[amount] != -666:
#             return memo[amount]
#
#         res = MAX_UINT
#         for coin in coins:  # 做选择
#             # 状态转移 min(dp(amount-coin)|coin∈coins)
#             sub_pro = dp(amount-coin)
#             if sub_pro == -1: continue
#             res = min(res, sub_pro+1)
#
#         if res != MAX_UINT:
#             memo[amount] = res
#         else:
#             memo[amount] = -1
#
#         return memo[amount]
#
#     return dp(amount)


# 自底而上
# 状态转移 dp[i] = min(dp[i], dp[i-coin]+1)
def coinChange(coins, amount):
    dp = [amount+1 for _ in range(amount+1)]  # 凑成i元至少需要dp[i]个硬币
    # base case
    dp[0] = 0
    for i in range(1, len(dp)):
        for coin in coins:
            if (i-coin) < 0: continue  # 当前硬币凑不到i元
            dp[i] = min(dp[i], dp[i-coin]+1)

    for i in range(len(dp)):
        if dp[i] == amount+1:
            dp[i] = -1

    return dp[amount]


coins = [1, 2, 5]
amount = 100
print("利用coins={}, 目标amount={}, 所需要最少零钱个数为 {}".format(coins, amount, coinChange(coins, amount)))

# L23: 最大子数组和
def maxSubArray(nums):
    dp = [i for i in nums]  # nums[:i]的最大子数组和为di[i] 走不通 -> 以nums[i]为结尾的最大子数组和为dp[i]
    for i in range(1, len(arr)):
        dp[i] = max(dp[i], dp[i-1]+nums[i])

    return max(dp)

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("{} 最大子数组和为 {}".format(arr, maxSubArray(arr)))

# L300: 最长递增子序列 LIS
def lengthOfLIS(nums):
    dps = [1 for i in range(len(nums))]  # 以nums[i]为结尾的最长递增子序列为长度为dps[i]
    for i in range(0, len(nums)):
        for j in range(0, i):
            if nums[i] > nums[j]:
                dps[i] = max(dps[i], dps[j]+1)

    return max(dps)

seq = [1, 4, 3, 4, 2, 3]
print("{} 最长递增子序列 {}".format(seq, lengthOfLIS(seq)))


# L1143: 最长公共子序列
def longestCommonSubsequence(text1, text2):
    m = len(text1)
    n = len(text2)
    memo = [[-1 for j in range(n)] for i in range(m)]

    def dp(i, j):  # 计算text1[i:]和text2[j:]的最长公共子序列长度
        # legal idx

        # base case
        if i == m or j == n:
            return 0

        # check memo
        if memo[i][j] != -1:
            return memo[i][j]

        # condition trans
        if text1[i] == text2[j]:
            memo[i][j] = 1 + dp(i+1, j+1)
        else:
            memo[i][j] = max(dp(i+1, j), dp(i, j+1), dp(i+1, j+1))

        return memo[i][j]

    return dp(0, 0)


t1 = "abcdefa"
t2 = "bdefc"
print("{} {} 最长公共子序列长度 {}".format(t1, t2, longestCommonSubsequence(t1, t2)))


# L583: 两个字符串的删除操作
def minDistance(word1, word2):
    m = len(word1)
    n = len(word2)

    lcs = longestCommonSubsequence(word1, word2)
    # 将word1删除到最长公共子序列需要 m-lcs 步
    # 将word2删除到最长公共子序列需要 n-lcs 步
    # 所以 删除的次数为 m-lcs + n-lcs
    return m+n-2*lcs


w1 = "sea"
w2 = "eat"
print("{} {} 最小删除操作数为 {}".format(w1, w2, minDistance(w1, w2)))


def minimumDeleteSum(s1, s2):
    m = len(s1)
    n = len(s2)

    memo = [[-1 for j in range(n)] for i in range(m)]

    def dp(i, j):  # s1[:i]
        res = 0
        if i >= m:
            for k in range(j, len(s2)):
                res += ord(s2[k])
            return res

        if j >= n:
            for k in range(i, len(s1)):
                res += ord(s1[k])
            return res

        if memo[i][j] != -1:
            return memo[i][j]

        if s1[i] == s2[j]:  # 在LCS里，不用删除
            memo[i][j] = dp(i+1, j+1)
        else:
            memo[i][j] = min(ord(s1[i])+dp(i+1, j), ord(s2[j])+dp(i, j+1))

        return memo[i][j]

    return dp(0, 0)

print("{} {} 最小ASCII删除和为 {}".format(w1, w2, minimumDeleteSum(w1, w2)))


# L354: 俄罗斯套娃信封 LIS变体，按x升序,x相同时按y降序，再对y执行LIS
def maxEnvelopes(evelopes):
    evelopes = list(sorted(evelopes, key=lambda x: x[1], reverse=True))
    evelopes = list(sorted(evelopes, key=lambda x: x[0]))

    dps = [1 for _ in range(len(evelopes))]
    for i in range(len(evelopes)):
        for j in range(i):
            if evelopes[i][1] > evelopes[j][1]:
                dps[i] = max(dps[j]+1, dps[i])

    return max(dps)

eves = [[4,6],[4,5],[6,7],[2,3],[1,1], [1,7]]
print("{} 最大套娃信封个数为 {}".format(eves, maxEnvelopes(eves)))


# L64: 最小路径和
def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    memo = [[-666 for j in range(n)] for i in range(m)]

    def dp(i, j):
        # 索引合法判断
        if i < 0 or j < 0:
            return MAX_UINT

        # base case
        if i == 0 and j == 0:  # 到达左上角起点
            return grid[0][0]

        # 查备忘录
        if memo[i][j] != -666:
            return memo[i][j]

        # 状态转移
        memo[i][j] = min(dp(i-1, j), dp(i, j-1)) + grid[i][j]

        return memo[i][j]

    # 自顶而下的调用dp
    return dp(m-1, n-1)  # 右下角终点


grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print("{} 的最小路径和为 {}".format(grid, minPathSum(grid)))


# L72：编辑距离  设两个字符串分别为 s1="rad" s2="apple" 通过 替换、删除、插入、不变将s1变成s2
# 分析：这是一个字符串DP问题，设置两个指针i,j指向两个字符串的最后，然后一步步往前走，缩小子问题的规模。
def minDistance(s1, s2):
    # 初始化备忘录
    memo = [[-1 for j in range(len(s2))] for i in range(len(s1))]

    # 定义DP函数：返回s1[0:i]和s2[0:j]的最小编辑距离
    def dp(i, j):
        # base case
        if i == -1: return j+1
        if j == -1: return i+1
        # 备忘录里有就直接返回
        if memo[i][j] != -1:
            return memo[i][j]

        if s1[i] == s2[j]:  # 元素相等
            memo[i][j] = dp(i-1, j-1)
        else:
            memo[i][j] = min(
                dp(i, j-1) + 1,  # s1(i)插入
                dp(i-1, j) + 1,  # s1(i)删除
                dp(i-1, j-1) + 1 # 替换
                )

        return memo[i][j]

    return dp(len(s1)-1, len(s2)-1)

s1 = "rad"
s2 = "apple"
print("{} {} 编辑距离 {} ".format(s1, s2, minDistance(s1, s2)))

# L931：下降路径最小和
def minFallingPathSum(matrix):
    m = len(matrix)
    n = len(matrix[0])
    res = MAX_UINT

    memo = [[-666 for j in range(n)] for i in range(m)]
    # 从matrix[0][:]往下落，落到matrix[i][j]的最小路径和为dp(i, j)
    def dp(i, j):
        # 合法索引判断
        if i < 0 or j < 0 or i >= m or j >= n:
            return MAX_UINT

        # base case
        if i == 0:
            return matrix[i][j]

        # 查找备忘录
        if memo[i][j] != -666:
            return memo[i][j]

        # 状态转移
        memo[i][j] = matrix[i][j] + min(dp(i-1, j-1), dp(i-1, j), dp(i-1, j+1))

        return memo[i][j]

    # 自顶而下的递归调用dp
    # 终点的位置 在matrix[m-1,:]行的任意一列
    for j in range(n):
        res = min(res, dp(m-1, j))
    return res

grid = [[1,2,3], [1,4,0], [2,1,1]]
print("{} 最小下降距离 {}".format(grid, minFallingPathSum(grid)))

def calculateMinimumHP():
    pass